package a06_栈与队列;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

import static jdk.nashorn.internal.objects.NativeRegExp.test;

/**
 * <p>
 * a07_滑动窗口最大值复习2
 * </p>
 *
 * @author flyduck
 * @since 2024/12/30
 */
public class a07_滑动窗口最大值复习2 {

    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();
        deque.push(1);
        deque.push(2);
        deque.push(3);
        System.out.println(deque.peekFirst());//3

        int[] nums = new int[]{1,-1};
        a07_滑动窗口最大值复习2 test = new a07_滑动窗口最大值复习2();
        int[] ints = test.maxSlidingWindow(nums, 1);
        System.out.println(Arrays.toString(ints));
    }

    //注意点：
    //resultIdx要用专门的索引
    //先将k个元素放入deque，再另一个循环进入之前，先获取最大值，并将resultIdx++
    //第二个循环进去后，先push后pop最后再getMax，要不然有问题
    public int[] maxSlidingWindow(int[] nums, int k) {
        MyDeque3 myDeque3 = new MyDeque3();

        int[] result = new int[nums.length - k + 1];

        int slowIdx = 0;//窗口起始索引
        int fastIdx = 0;//窗口结束索引
        int resultIdx = 0;//要赋值的索引
        //1,2,3,4,5,6,7,8,9 3
        //slowIdx
        //      fastIdx
        while (fastIdx  < k) {
            myDeque3.push(nums[fastIdx]);
            fastIdx++;
        }

        result[resultIdx] = myDeque3.getMax();
        resultIdx++;

        //1,2,3,4,5,6,7,8,9 3
        //slowIdx
        //      fastIdx

        while (fastIdx < nums.length) {
            myDeque3.push(nums[fastIdx]);
            myDeque3.pop(nums[slowIdx]);
            result[resultIdx] = myDeque3.getMax();
            slowIdx++;
            fastIdx++;
            resultIdx++;
        }
        return result;

    }
}

//队列存放可能成为最大值的数
class MyDeque3{

    private Deque<Integer> deque;

    public MyDeque3() {
        this.deque = new LinkedList<>();
    }

    //如果队列最后有比push进来的元素小的元素的时候，就pop出去
    public void push(int val){
        while (!deque.isEmpty() && deque.peekFirst() < val) {
            deque.pollFirst();
        }
        deque.push(val);
    }

    //如果队列的最前面刚好是val，才去pop
    public void pop(int val){
        if (!deque.isEmpty() && deque.peekLast() == val) {
            deque.pollLast();
        }
    }

    //队列的最前面就是最大值
    public int getMax(){
        return deque.peekLast();
    }
}
